package project;

import java.util.ArrayList;
import java.util.Random;

public class KmodesAlgorithm {

	private String[][] data;
	private int[] resultTbl;
	private String[][] Modes;
	private int k;

	public KmodesAlgorithm(String[][] data, int k, int s) {
		this.data = data;
		this.k = k;
		initResultTable();
		switch (s) {
		case 0:
			selectKModes0();
			break;
		case 1:
			selectKModes1();
			break;
		case 2:
			selectKModes2();
			break;
		default:
			System.out.println("have not implement yet!");
			break;
		}
	}

	public String[][] getModes() {
		return Modes;
	}

	public void setModes(String[][] modes) {
		Modes = modes;
	}

	public int[] getResultTbl() {
		return resultTbl;
	}

	public void setResultTbl(int[] resultTbl) {
		this.resultTbl = resultTbl;
	}

	public void selectKModes0() {
		System.out
				.println("\n-------------------------------------- Step 1: chooses randomly initial K-modes from given dataset with k = "
						+ k
						+ " ------------------------------------------------------");
		Random rand = new Random();
		Modes = new String[k][data[0].length];
		for (int i = 0; i < k; i++) {
			String temp[] = data[rand.nextInt(data.length)];
			for (int j = 0; j < Modes[0].length; j++) {
				Modes[i][j] = temp[j];
			}
		}
	}

	public void selectKModes1() {
		System.out
				.println("\n-------------------------------------- Step 1: chooses randomly initial K-modes from given dataset with k = "
						+ k
						+ " ------------------------------------------------------");
		Random rand = new Random();
		boolean isDuplicate = false;
		Modes = new String[k][data[0].length];

		for (int i = 0; i < k; i++) {

			do {
				isDuplicate = false;
				String temp[] = data[rand.nextInt(data.length)];
				for (int j = 0; j < i; j++) {
					if (distance(Modes[j], temp) == 0) {
						isDuplicate = true;
					}
				}

				for (int j = 0; j < Modes[0].length; j++) {
					Modes[i][j] = temp[j];
				}
			} while (isDuplicate);

		}

	}

	public void selectKModes1Optimization() {
		System.out
				.println("\n-------------------------------------- Step 1: chooses randomly initial K-modes from given dataset with k = "
						+ k
						+ " ------------------------------------------------------");
		Random rand = new Random();
		boolean isDuplicate = false;
		Modes = new String[k][data[0].length];

		for (int i = 0; i < k; i++) {

			do {
				isDuplicate = false;
				String temp[] = data[rand.nextInt(data.length)];
				for (int j = 0; j < i; j++) {
					if (distance(Modes[j], temp) < 10) {
						isDuplicate = true;
					}
				}

				for (int j = 0; j < Modes[0].length; j++) {
					Modes[i][j] = temp[j];
				}
			} while (isDuplicate);

		}
	}

	public void selectKModes2() {
		System.out
				.println("\n-------------------------------------- Step 1.2: chooses randomly initial K-modes from given dataset with k = "
						+ k
						+ " ------------------------------------------------------");
		Modes = new String[k][data[0].length];

		ArrayList<String[]> frequencytbl = new ArrayList<String[]>();
		String[] temp = new String[data.length];
		for (int i = 0; i < data[0].length; i++) {

			for (int j = 0; j < data.length; j++) {
				temp[j] = data[j][i];
			}

			frequencytbl.add(DataManipulation.removeDuplicatesStr(temp));
		}
		for (String[] arr : frequencytbl) {
			int[] frequencyarray = new int[arr.length];
			for (int i = 0; i < arr.length; i++) {

				for (int j = 0; j < data.length; j++) {
					temp[j] = data[j][frequencytbl.indexOf(arr)];
				}

				frequencyarray[i] = DataManipulation.count(arr[i], temp);
				System.out.print(arr[i] + ":f=" + frequencyarray[i] + ";");
			}
			ModifiedQuickSort mqs = new ModifiedQuickSort();
			mqs.sort(frequencyarray, arr);
			DataManipulation.reverse(mqs.array);
			for (int i = 0; i < arr.length; i++) {
				arr[i] = mqs.array[i];
			}
			System.out.println();
		}

		if (k <= data[0].length) {
			for (int i = 0; i < k; i++) {
				Modes[i][i] = frequencytbl.get(i)[0];
			}
			for (int i = 0; i < Modes.length; i++) {
				for (int j = 0; j < Modes[0].length; j++) {
					System.out.print(Modes[i][j] + " ");
				}
				System.out.println();
			}

			for (int c = 0; c < k; c++) {
				if (c == 0) {
					int x = c;
					int y = 0;
					boolean down = true;
					for (int i = 0; i < frequencytbl.size(); i++) {
						if (i != x) {
							if (down) {
								if (frequencytbl.get(i).length == 1) {
									Modes[x][i] = frequencytbl.get(i)[0];
									y = 0;
								} else
									for (int j = 0; j < frequencytbl.get(i).length; j++) {
										if (!checkconflict(
												frequencytbl.get(i)[j], Modes,
												i)
												&& (j > y)) {

											Modes[x][i] = frequencytbl.get(i)[j];
											y = j;
											break;
										}
									}
								if (Modes[x][i] == null) {
									down = false;
								}
							}
							if (!down) {
								if (frequencytbl.get(i).length == 1) {
									Modes[x][i] = frequencytbl.get(i)[0];
									y = 0;
								} else
									for (int j = 0; j < frequencytbl.get(i).length; j++) {
										if (!checkconflict(
												frequencytbl.get(i)[j], Modes,
												i)
												&& (j < y)) {
											Modes[x][i] = frequencytbl.get(i)[j];
											y = j;
										}
									}

								if (frequencytbl.get(data[0].length - 1)[0] != null) {
									down = true;
								}
							}
						}
					}
				}
				if ((0 < c) && (c < k - 1)) {
					int x = c;
					int y = 0;
					boolean down = true;
					System.out.println("asfsdfgd");
					for (int i = c; i >= 0; i--) {
						if (i != x) {
							if (down) {
								if (frequencytbl.get(i).length == 1) {
									Modes[x][i] = frequencytbl.get(i)[0];
									y = 0;
								} else
									for (int j = 0; j < frequencytbl.get(i).length; j++) {
										if (!checkconflict(
												frequencytbl.get(i)[j], Modes,
												c)
												&& (j > y)) {
											Modes[x][i] = frequencytbl.get(i)[j];
											y = j;
											break;
										}
									}
								if (Modes[x][i] == null) {
									down = false;
								}
							}
							if (!down) {
								if (frequencytbl.get(i).length == 1) {
									Modes[x][i] = frequencytbl.get(i)[0];
									y = 0;
								} else
									for (int j = 0; j < frequencytbl.get(i).length; j++) {
										if (!checkconflict(
												frequencytbl.get(i)[j], Modes,
												c)
												&& (j < y)) {
											Modes[x][i] = frequencytbl.get(i)[j];
											y = j;
											// break;
										}
									}
								if (frequencytbl.get(data[0].length - 1)[0] != null) {
									down = true;
								}
							}
						}
					}
					for (int i = c; i < frequencytbl.size(); i++) {
						if (i != x) {
							if (down) {
								if (frequencytbl.get(i).length == 1) {
									Modes[x][i] = frequencytbl.get(i)[0];
									y = 0;
								} else
									for (int j = 0; j < frequencytbl.get(i).length; j++) {
										if (!checkconflict(
												frequencytbl.get(i)[j], Modes,
												c)
												&& (j >= y)) {

											Modes[x][i] = frequencytbl.get(i)[j];
											y = j;
											break;
										}
									}

								if (Modes[x][i] == null) {
									down = false;
								}
							}
							if (!down) {
								if (frequencytbl.get(i).length == 1) {
									Modes[x][i] = frequencytbl.get(i)[0];
									y = 0;
								} else
									for (int j = 0; j < frequencytbl.get(i).length; j++) {
										if (!checkconflict(
												frequencytbl.get(i)[j], Modes,
												c)
												&& (j < y)) {
											Modes[x][i] = frequencytbl.get(i)[j];
											y = j;
											// break;
										}
									}
								if (frequencytbl.get(data[0].length - 1)[0] != null) {
									down = true;
								}
							}
						}
					}
				}

				if (c == k - 1) {
					int x = c;
					int y = 0;
					boolean down = true;
					System.out.println("asfsdfgd");
					for (int i = c; i >= 0; i--) {
						if (i != x) {
							if (down) {
								if (frequencytbl.get(i).length == 1) {
									Modes[x][i] = frequencytbl.get(i)[0];
									y = 0;
								} else
									for (int j = 0; j < frequencytbl.get(i).length; j++) {
										if (!checkconflict(
												frequencytbl.get(i)[j], Modes,
												c)
												&& (j > y)) {
											Modes[x][i] = frequencytbl.get(i)[j];
											y = j;
											break;
										}
									}
								if (Modes[x][i] == null) {
									down = false;
								}
							}
							if (!down) { 
								if (frequencytbl.get(i).length == 1) {
									Modes[x][i] = frequencytbl.get(i)[0];
									y = 0;
								} else
									for (int j = 0; j < frequencytbl.get(i).length; j++) {
										if (!checkconflict(
												frequencytbl.get(i)[j], Modes,
												c)
												&& (j < y)) {
											Modes[x][i] = frequencytbl.get(i)[j];
											y = j;
										}
									}
								if (frequencytbl.get(data[0].length - 1)[0] != null) {
									down = true;
								}
							}
						}
					}
					for (int i = c; i < frequencytbl.size(); i++) {
						if (i != x) {
							if (down) {
								if (frequencytbl.get(i).length == 1) {
									Modes[x][i] = frequencytbl.get(i)[0];
									y = 0;
								} else
									for (int j = 0; j < frequencytbl.get(i).length; j++) {
										if (!checkconflict(
												frequencytbl.get(i)[j], Modes,
												c)
												&& (j >= y)) {

											Modes[x][i] = frequencytbl.get(i)[j];
											y = j;
											break;
										}
									}
								if (Modes[x][i] == null) {
									down = false;
								}
							}
							if (!down) {
								if (frequencytbl.get(i).length == 1) {
									Modes[x][i] = frequencytbl.get(i)[0];
									y = 0;
								} else
									for (int j = 0; j < frequencytbl.get(i).length; j++) {
										if (!checkconflict(
												frequencytbl.get(i)[j], Modes,
												c)
												&& (j < y)) {
											Modes[x][i] = frequencytbl.get(i)[j];
											y = j;
										}
									}
								if (frequencytbl.get(data[0].length - 1)[0] != null) {
									down = true;
								}
							}
						}
					}
				}
			}
			for (int z = 0; z < Modes.length; z++) {
				for (int j = 0; j < Modes[0].length; j++) {
					if (Modes[z][j] == null) {
						Modes[z][j] = frequencytbl.get(z)[0];
					}
				}
			}

			for (int i = 0; i < k; i++) {
				int dis = data.length;
				int index = 0;
				for (int j = 0; j < data.length; j++) {
					if ((distance(Modes[i], data[j]) < dis)) {
						for (int z = 0; z < Modes.length; z++) {
							if (distance(Modes[i], Modes[z]) != 0) {
								dis = distance(Modes[i], data[j]);
								index = j;
							}
						}
					}
				}

				for (int j = 0; j < Modes[0].length; j++) {
					Modes[i][j] = data[index][j];
				}
			}

			System.out.println();
			for (int z = 0; z < Modes.length; z++) {
				for (int j = 0; j < Modes[0].length; j++) {
					System.out.print(Modes[z][j] + " ");
				}
				System.out.println();
			}
		}


		System.out.println();
		for (String[] arr : frequencytbl) {
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
		}

	}

	public void initResultTable() {
		System.out.println("\ninit result table (array that indicates Obj <=> Mode)");
		resultTbl = new int[data.length];
		for (int i = 0; i < data.length; i++) {
			resultTbl[i] = 0;
			System.out.println("Oject " + i + " = " + resultTbl[i]);
		}
	}

	public void checkAndUpdate() {
		System.out.println("\n--------------------------------------------------- Step 2&3&4 : recheck and relocate K-modes (on-the-fly-update) ---------------------------------------------------------------------------------\n");
		int loop = 0;
		boolean changed = true;
		int[] tempresulttbl = new int[data.length];

		while (changed == true) {

			System.out.println("loop " + (loop + 1) + ":");

			for (int i = 0; i < data.length; i++) {
				System.out.println("Alocating Object " + i);
				int distance = data[0].length + 1;

				for (int kno = 0; kno < k; kno++) {
					int temp = 0;
					System.out.print(" with K-Mode " + kno);

					temp = distance(Modes[kno], data[i]);
					System.out.println(" have distance = " + temp);
					if (temp <= distance) {
						distance = temp;
						tempresulttbl[i] = kno;
					}
				}
				System.out.println("=>Min distance :" + distance + "\n");
			}

			System.out.println("before check & update!");
			DataManipulation.printIntArray(resultTbl);
			System.out.println("\nafter check & update!");
			DataManipulation.printIntArray(tempresulttbl);

			changed = false;
			for (int i = 0; i < data.length; i++) {
				if (tempresulttbl[i] != resultTbl[i]) {
					changed = true;
					break;
				}
			}
			if (changed == true) {
				System.out.println("\nupdate modes");
				for (int i = 0; i < resultTbl.length; i++) {
					resultTbl[i] = tempresulttbl[i];
				}

				for (int i = 0; i < Modes.length; i++) {
					for (int a = 0; a < data[0].length; a++) {
						int max = 0;
						for (int x = 0; x < data.length; x++) {
							if (resultTbl[x] == i) {
								int temp1 = 0;
								for (int y = x; y < data.length; y++) {
									if ((resultTbl[y] == i)
											&& (data[x][a].equals(data[y][a]))) {
										temp1++;
									}
								}
								if (temp1 > max) {
									max = temp1;
									Modes[i][a] = data[x][a];
								}
							}
						}
						System.out.println("| cluster " + (i + 1)
								+ " at attribute " + (a + 1) + " is value "
								+ Modes[i][a] + " ( max freq: " + max + ")");
					}
				}

				System.out.println("\nUpdate K-Mode");
				DataManipulation.printMode(Modes);
			}

			loop++;
		}
		System.out.println("loop = " + (loop + 1));
	}

	private int distance(String[] array1, String[] array2) {
		int dis = 0;
		for (int i = 0; i < array1.length; i++) {
			if (!array1[i].equals(array2[i])) { 
				dis++;
			}
		}
		return dis;
	}

	public int[] statistic() {
		int array[] = new int[k];
		int count;
		for (int i = 0; i < k; i++) {
			count = 0;
			for (int j = 0; j < resultTbl.length; j++) {
				if (resultTbl[j] == i) {
					count++;
				}
			}
			array[i] = count;
			System.out.println("Mode " + (i + 1) + " have :" + count
					+ " instances!");
		}
		return array;
	}

	public static boolean checkconflict(String str, String[][] Modes, int col) {
		for (int i = 0; i < Modes.length; i++) {
			if ((Modes[i][col] != null) && Modes[i][col].equals(str)) {
				return true;
			}
		}
		return false;
	}

	public static boolean checkconflictall(String[] str, String[][] Modes,
			int col) {
		boolean bool = false;
		for (int i = 0; i < str.length; i++) {
			if (checkconflict(str[i], Modes, col)) {
				bool = true;
			}
		}
		for (int i = 0; i < Modes.length; i++) {
			if ((Modes[i][col] == null)) {
				bool = true;
			}
		}
		return bool;
	}

}
